package leet40combinesumiii

import "sort"

// https://leetcode.cn/problems/combination-sum-ii/description/
// 完全使用copilot自动生成的代码
// 该代码的path是以参数的形式传递的，而不是以全局变量的形式，这样可以避免在递归过程中出现路径共享的问题。
// 那该代码中的path能不能以全局变量的形式呢？答案是可以的，但是需要注意在每次递归之前都要清空path，否则会出现路径共享的问题。
func CombinationSum2(candidates []int, target int) [][]int {
	var result [][]int
	var backtrack func(start int, target int, path []int)
	backtrack = func(start int, target int, path []int) {
		if target == 0 {
			// 找到一个组合
			combination := make([]int, len(path))
			copy(combination, path)
			result = append(result, combination)
			return
		}
		for i := start; i < len(candidates); i++ {
			if candidates[i] > target {
				break
			}
			// 处理重复元素 - 精华所在!!!!!!!
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			// 选择当前元素
			backtrack(i+1, target-candidates[i], append(path, candidates[i]))
		}
	}
	// 排序，方便剪枝和去重
	sort.Ints(candidates)
	backtrack(0, target, []int{})
	return result
}
